package cn.initcap.algorithm.swing.sort.merge;

import cn.initcap.algorithm.swing.AlgoVisHelper;
import cn.initcap.algorithm.swing.BaseAlgoFrame;
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.util.Arrays;

/**
 * @author initcap
 * @date 8/1/19 3:10 PM
 */
public class AlgoVisualizer {

    private static int DELAY = 40;
    private MergeSortData data;
    private BaseAlgoFrame frame;

    public AlgoVisualizer(int sceneWidth, int sceneHeight, int n) {

        // 初始化数据
        data = new MergeSortData(n, sceneHeight);

        // 初始化视图
        EventQueue.invokeLater(() -> {
            frame = new BaseAlgoFrame("Merge Sort Visualization", sceneWidth, sceneHeight) {
                @Override
                public void draw(Graphics graphics) {
                    Graphics2D g2d = (Graphics2D) graphics;
                    int w = sceneWidth / data.N();
                    for (int i = 0; i < data.N(); i++) {
                        if (i >= data.l && i <= data.r) {
                            AlgoVisHelper.setColor(g2d, AlgoVisHelper.GREEN);
                        } else {
                            AlgoVisHelper.setColor(g2d, AlgoVisHelper.GREY);
                        }

                        if (i >= data.l && i <= data.mergeIndex) {
                            AlgoVisHelper.setColor(g2d, AlgoVisHelper.RED);
                        }

                        AlgoVisHelper.fillRectangle(g2d, i * w, sceneHeight - data.get(i), w - 1, data.get(i));
                    }
                }
            };

            new Thread(() -> {
                run();
            }).start();
        });
    }

    public static void main(String[] args) {

        int sceneWidth = 800;
        int sceneHeight = 800;
        int n = 100;

        new AlgoVisualizer(sceneWidth, sceneHeight, n);
    }

    public void run() {

        setData(-1, -1, -1);

        for (int sz = 1; sz < data.N(); sz *= 2) {
            for (int i = 0; i < data.N() - sz; i += sz + sz)
            // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
            {
                merge(i, i + sz - 1, Math.min(i + sz + sz - 1, data.N() - 1));
            }
        }

        this.setData(0, data.N() - 1, data.N() - 1);
    }

    private void merge(int l, int mid, int r) {

        int[] aux = Arrays.copyOfRange(data.numbers, l, r + 1);

        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {

            // 如果左半部分元素已经全部处理完毕
            if (i > mid) {
                data.numbers[k] = aux[j - l];
                j++;
                // 如果右半部分元素已经全部处理完毕
            } else if (j > r) {
                data.numbers[k] = aux[i - l];
                i++;
                // 左半部分所指元素 < 右半部分所指元素
            } else if (aux[i - l] < aux[j - l]) {
                data.numbers[k] = aux[i - l];
                i++;
                // 左半部分所指元素 >= 右半部分所指元素
            } else {
                data.numbers[k] = aux[j - l];
                j++;
            }

            setData(l, r, k);
        }
    }

    private void setData(int l, int r, int mergeIndex) {
        data.l = l;
        data.r = r;
        data.mergeIndex = mergeIndex;

        frame.render(data);
        AlgoVisHelper.pause(DELAY);
    }
}